#include <fstream>
#include <vector>
#include <string>

using namespace std;

bool CanWin (int a, int b)
{
	if (a==0 ||  b==0)
		return true;

	if (a == b)
		return false;

	// a > b
	int k =a / b;

	if (k>1)
		return true;

	int mod =a % b;
	if (mod == 0)
		return true;

	bool canWin = CanWin(b, mod);
	if (!canWin)
		return true;
	
	return false; 
}

int FindFirstZero (int a, int an, int max, int min)
{
	bool anWin = CanWin (a, an); 

	if (anWin) // 1
	{
		bool ana1Win = CanWin (a, an+1); 
		if (!ana1Win)
			return an +1;

		int newAn =(max+an)/2;
		return FindFirstZero (a, newAn, max, an);
	}
	else // 0
	{
		bool an_1Win = CanWin (a, an-1); 
	
		if (an_1Win)
			return an;
		
		int newAn =(min+an)/2;
		return FindFirstZero (a, newAn, an, min);
	}
}

int FindFirstZero (int a)
{
	double da =a;
	da *= 0.6180339887498948482045868;
	da += 0.99999999999;

	return (int)da;
}

int Calc (int a, int b1, int b2)
{
	if (a ==1)
	{
		if (b1 ==1)
			return b2 -b1;

		return b2 -b1 +1;
	}

	//int firstZero = FindFirstZero (a, a/2, a, 1);
	int firstZero = FindFirstZero (a);
	int lastZero = firstZero + a-1;

	int n = b2 -b1 +1;

	if (firstZero > b2)
	{
		return n;
	}

	if (lastZero < b1)
	{
		return n;
	}

	if (firstZero <= b1 && lastZero>=b2)
	{
		return 0;
	}

	if (firstZero >= b1 && lastZero<=b2)
	{
		return n -a;
	}

	if (firstZero < b1 && lastZero>=b1)
	{
		return b2-lastZero;
	}

	if (firstZero <= b2 && lastZero>b2)
	{
		return firstZero -b1;
	}

	return n;
}

__int64 Calc (int a1, int a2, int b1, int b2)
{
	printf ("%d, %d, %d, %d\n", a1, a2, b1, b2);

	__int64 n =0;

	if (a2-a1<b2-b1)
	{
		for (int a=a1; a<=a2; a++)
		{
			n += Calc (a, b1, b2);
		}
	}
	else
	{
		for (int b=b1; b<=b2; b++)
		{
			n += Calc (b, a1, a2);
		}
	}

	return n;
}


void RunC(const char* fnameIn, const char* fnameOut)
{
	ifstream fin(fnameIn);
	
	int caseCount;
	fin >> caseCount;

	ofstream fout(fnameOut);
	int a1, a2, b1, b2;

	for (int i=0; i<caseCount; i++)
	{
		fin >>a1>>a2>>b1>>b2;

		__int64 r =Calc(a1, a2, b1, b2);

		fout<<"Case #"<<i+1<<": ";
		fout<< r;
		fout<<"\n";
	}
}



//int main(int argc, int argv[])
//{
//	RunC("C-small-practice.in", "C-small-practice.out");
//	RunC("C-large-practice.in", "C-large-practice.out");
//
//	return 0;
//}
